package trees;

public class TreeInArray {

	static class Tree {

		int value;
		Tree left, right;

		public Tree(int v) {
			this.value = v;
		}

		public String toString() {
			return String.valueOf(value);
		}

	}

	// Given a balanced binary tree implemented with standard child node
	// references, re-implement in array format.

	public static void main(String args[]) {

		Tree t1 = new Tree(7);
		Tree t2 = new Tree(5);
		Tree t3 = new Tree(10);
		t1.left = t2;
		t1.right = t3;
		Tree t4 = new Tree(3);
		Tree t5 = new Tree(15);
		t2.left = t4;
		t3.right = t5;
		Tree t6 = new Tree(1);
		Tree t7 = new Tree(4);
		t4.left = t6;
		t4.right = t7;

		Tree[] array = convertTreeToArray(t1);

		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + " ");
		}
	}

	private static Tree[] convertTreeToArray(Tree root) {

		int depth = getTreeDepth(root);
		Tree[] array = new Tree[calculateRequiredSize(depth)];

		traverse(root, array, 0);

		return array;
	}

	private static void traverse(Tree t, Tree[] array, int position) {

		if (t != null) {
			array[position] = t;
			traverse(t.left, array, position * 2 + 1);
			traverse(t.right, array, position * 2 + 2);
		}

	}

	public static int traverse(Tree t) {

		int depth = 0;
		if (t != null) {
			depth = 1;
			int d1 = traverse(t.left);
			int d2 = traverse(t.right);

			depth += d1 > d2 ? d1 : d2;
		}

		return depth;
	}

	public static int getTreeDepth(Tree t) {

		int depth = 0;
		if (t != null) {

			int d1 = traverse(t.left);
			int d2 = traverse(t.right);

			depth += d1 > d2 ? d1 : d2;
		}
		return depth;
	}

	private static int calculateRequiredSize(int depth) {

		final int q = 2;
		return (int) (1.0 * (1 - Math.pow(q, depth + 1)) / (1 - q));

	}

}
